package com.zdp.util;

public class QuickSort {
    public static void main(String[] args) {
        QuickSort demo = new QuickSort();
        int[] nums = new int[] {
                5,6,7,2,3,1,56,10
        };
        int[] nums1 = new int[] {
                5,6,7,2,3,1,56,10
        };
        demo.quickSort(nums,0,nums.length-1);
        demo.quickSort1(nums1,0,nums.length-1);
        for(int i : nums){
            System.out.print(i+",");
        }
        System.out.println();
        for(int i : nums1){
            System.out.print(i+",");
        }
    }

    public void quickSort(int[] nums,int left,int right){
        if(left<right){
            int partition = getPartition(nums,left,right);
            // 左边递归
            quickSort(nums,left,partition-1);
            // 右边递归
            quickSort(nums,partition+1,right);
        }
    }
    public int getPartition(int[] nums,int left,int right){
        // 三数取中法
        int partition = left+ ((right-left)>>1);
        // 将基准值放在最后
        swap(nums,partition,right);
        int i = left-1;
        int x = nums[right];
        for(int j=left;j<right;j++){
            if(nums[j]<=x){
                swap(nums,++i,j);
            }
        }
        swap(nums,++i,right);
        return i;
    }

    public void quickSort1(int[] nums,int left,int right){
        if(left<right){
            int partition = getPartition1(nums,left,right);
            // 左边递归
            quickSort1(nums,left,partition-1);
            // 右边递归
            quickSort1(nums,partition+1,right);
        }
    }
    // 另一个方式获取枢轴
    public int getPartition1(int[] nums,int left,int right){
        int partition = left+ ((right-left)>>1);
        System.out.println(partition);
        swap(nums,left,partition);
        int x = nums[left];
        // 将基准值放在左边
        while(left<right){
            while(left<right&&nums[right]>=x)
                right--;
            // 交换
            nums[left] = nums[right];
            // 将左边的基准值较大的那个数 换到右边
            while(left<right&&nums[left]<=x){
                left++;
            }
            nums[right] = nums[left];
        }
        nums[left] = x;
        return left;
    }

    public void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

